package com.leetcode.leetcode2;

import java.util.Arrays;

/**
 *  合并k个升序链表
 * @author: luhd
 * @create: 2021-09-06
 */
public class Practice23 {
    public static void main(String[] args) {

    }
    public static class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }
    public static ListNode mergeKLists(ListNode[] lists) {
        // 利用归并排序的递归思想
        int len = lists.length;
        if(len == 1) return lists[0];
        if(len == 0) return null;
        // 拆分的界定值
        int mid = len / 2;
        // 将链表拆分  成两个链表   分为左右链表  直至分到不能再分
        ListNode[] left = Arrays.copyOfRange(lists,0,mid);  //不包含数组下标为mid的
        ListNode[] right = Arrays.copyOfRange(lists,mid,len);
        // 运用递归
        return mergeListNode(mergeKLists(left),mergeKLists(right));
    }
    // 合并两个有序链表
    public static ListNode mergeListNode(ListNode l1, ListNode l2){
        ListNode head = new ListNode(0);    // 链表头节点
        ListNode tail = head;   // 链表尾节点
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                tail.next = l1;
                l1 = l1.next;
                tail = tail.next;
            } else{
                tail.next = l2;
                l2 = l2.next;
                tail = tail.next;
            }
        }
        while(l1!=null){
            tail.next = l1;
            l1 = l1.next;
            tail = tail.next;
        }
        while(l2!=null){
            tail.next = l2;
            l2 = l2.next;
            tail = tail.next;
        }
        return head.next;
    }
}
